//
// Created by ASUS on 2024/4/18/星期四.
//

/*
暴力做法是枚举数组a的所有排列，对每个排列计算和题目有关的值，时间复杂度（通常来说）是O(n⋅n!)。可以解决n≤10 的问题。
状压 DP 可以把时间复杂度（通常来说）优化至O(n⋅2^n)。可以解决n≤20 的问题。
一般定义f[S] 表示已经排列好的元素（下标）集合为S 时，和题目有关的最优值。通过枚举当前位置要填的元素来转移。
注意不需要额外的状态表示当前要填第几个位置，因为集合S 的大小就是当前要填的位置。
 */



#include <bits/stdc++.h>
using namespace std;

//记忆化搜索
//时间复杂度：O(n^2*2^n), 空间复杂度：O(n*2^n)
int countArrangement(int n) {
	int memo[1<<n][n+1];
	memset(memo,-1,sizeof memo);
	function<int(int,int)> dfs=[&](int mask,int j)->int{
		if(mask==0&&j==n) return 1;
		if(j>n) return 0;
		if(memo[mask][j]!=-1) return memo[mask][j];
		int res=0;
		for(int i=0;i<n;i++){
			if((mask>>i&1)&&((i+1)%(j+1)==0||(j+1)%(i+1)==0)){
				res+=dfs(mask^(1<<i),j+1);
			}
		}
		return memo[mask][j]=res;
	};
	return dfs((1<<n)-1,0);
}
//记忆化搜索
//时间复杂度：O(n*2^n), 空间复杂度：O(2^n)
int countArrangement1(int n) {
	int memo[1<<n];
	memset(memo,-1,sizeof memo);
	function<int(int)> dfs=[&](int mask)->int{
		if(mask==0) return 1;
		if(memo[mask]!=-1) return memo[mask];
		int j=n-__builtin_popcount(mask);
		int res=0;
		for(int i=0;i<n;i++){
			if((mask>>i&1)&&((i+1)%(j+1)==0||(j+1)%(i+1)==0)){
				res+=dfs(mask^(1<<i));
			}
		}
		return memo[mask]=res;
	};
	sqrt(n);
	return dfs((1<<n)-1);
}
//递推
//时间复杂度：O(n*2^n), 空间复杂度：O(2^n)
int countArrangement2(int n) {
	vector<int> f(1 << n);
	f[0] = 1;
	for (int st = 1; st < (1 << n); st++) {
		int j = __builtin_popcount(st);
		for (int i = 0; i < n; i++) {
			if ((st >> i & 1) && ((i+1) % j == 0 || j % (i+1) == 0)) {
				f[st] += f[st ^ (1 << i)];
			}
		}
	}
	return f.back();
}
//lc1947
//从mentors中选k个与students前k个匹配
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
	int m = students.size(), n = students[0].size();
	vector<int> f(1 << m, 0);
	for (int st = 1; st < (1 << m); st++) {
		int j = __builtin_popcount(st);
		for (int i = 0; i < m; i++) {
			if ((st >> i & 1)) {
				int res = 0;
				for (int k = 0; k < n; k++) {
					res += students[j - 1][k] == mentors[i][k];
				}
				f[st] = max(f[st], f[st ^ (1 << i)] + res);
			}
		}
	}
	return f.back();
}

//lc1799  选两个
int maxScore(vector<int>& nums) {
	int n = nums.size();
	vector<vector<int>> g(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			g[i][j] = gcd(nums[i], nums[j]);
		}
	}
	vector<int> f(1 << n, 0);
	for (int st = 1; st < (1 << n); st++) {
		int cnt = __builtin_popcount(st);
		if (cnt & 1) continue;
		for (int i = 0; i < n; i++) {
			if (st >> i & 1) {
				for (int j = i + 1; j < n; j++) {
					if (st >> j & 1) {
						f[st] = max(f[st], f[st ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
					}
				}
			}
		}
	}
	return f.back();
}


//lc2172
int maximumANDSum(vector<int>& nums, int numSlots) {
	int n = numSlots * 2, ans = 0;
	vector<int> f(1 << n);
	for (int st = 0; st < (1 << n); st++) {
		int j = __builtin_popcount(st);
		if (j >= nums.size())
			continue;
		for (int i = 0; i < n; i++) {
			if ((st >> i & 1) == 0) {
				f[st | (1 << i)] = max(f[st | (1 << i)], f[st] + ((i / 2 + 1) & nums[j]));
				ans = max(ans, f[st| (1 << i)]);
			}
		}
	}
	return ans;
}